#include <iostream>
using namespace std;
// https://leetcode.cn/problems/path-sum-iii/description/
// 437. 路径总和 III
// 给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
//路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0),left(NULL),right(NULL) {}
    TreeNode(int x): val(x),left(NULL),right(NULL) {}
};

class Solution {
public:
    // 在以root为根结点的二叉树中，寻找和为sum的路径，返回这样的路径个数
    int pathSum(TreeNode* root, int targetSum) {
        if(root == NULL)
            return 0;

        int res = findPath(root, targetSum);  // 这条路径包含root，并且路径的和为sum
        res += pathSum(root->left, targetSum);  // 不包含 root 结点，在root的右子树寻找其和为targetSum的路径
        res += pathSum(root->right, targetSum); // 不包含 root 结点，在root的右子树训中其和为targetSum的路径

        return res;
    }

private:
    // 在以node为根结点的二叉树中，寻找包含node的路径，和为sum
    // 返回这样的路径个数
    int findPath(TreeNode* node, long num) {    // 注意这里的要使用long，使用int会溢出
        if(node == NULL)
            return 0;

        int res = 0;
        if(node->val == num)
            res += 1;   // 结点可能是负数

        res += findPath(node->left, num - node->val);
        res += findPath(node->right, num - node->val);

        return res;
    }
};


int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
